A transmitter of a wireless communication system transmits data sequences in the order of a specific pattern by using interleaving without continuously transmitting them in their input order. Burst error frequently occurring on a wireless link can be shifted to random error by interleaving. In other words, in the wireless communication system, it is likely that a part of transmission data may be lost at one time by fading. If continuous data are lost at one time, this error cannot be corrected even if good error correction code is used. On the other hand, if error bits are sparse in sequences of transmission data, the error can be corrected using error correction code such as convolution code, turbo code, and LDPC (Lowe Density Parity Check) code. Accordingly, it is necessary to shift burst error to random error using interleaving.
Since interleaving means that data sequences are written in a memory and then read in the order different from the written order in accordance with a given rule, which is previously defined, it needs to generate a memory write address and a memory read address.
One of methods of generating a read address for interleaving includes a BRO (Bit Reverse Ordering) scheme. The BRO scheme means an operation scheme which shifts a digit of a decimal number to a binary number of M bits, reverses MSB to become LSB, and vice versa, with respect to full M bits, and then shifts the binary number to the decimal number. For example, the order of shifting a digit 3 of a decimal number in accordance with 5-bit BRO operation (M=5) is as follows. If a digit 3 is shifted to a binary number of 5 bits, it becomes ‘00011.’ If the bit order of ‘00011’ undergoes reverse ordering, it becomes ‘11000.’ If ‘11000’ is shifted to a decimal number, it becomes 24. Accordingly, the result of 5-bit BRO operation for a digit 3 of a decimal number becomes 24. As described above, the data sequences are output using the read address order after the write address is shifted to the read address using the BRO operation. In this case, since the order of the data sequences is changed, interleaving can be performed.
Equation 1 generally expresses the result of M-bit BRO interleaving when an interleaving depth, i.e., a size L of index set (0, 1, 2, . . . , L−1) is 2M. In this case, BRO (i, M) represents the result of M-bit BRO operation for a decimal number i.j=π(i)=BRO(i,M),i=0,1,2, . . . ,L−1  [Equation 1]
If the interleaving depth L is greater than 2M-1 and smaller than 2M, M-bit BRO operation is performed for indexes of 0˜(2M−1), and interleaving is performed for indexes greater than or equal to L by pruning. The following represents an algorithm for performing interleaving through M-bit BRO operation using pruning when L is 2M-1<L<2M.
i = 0for m=0 to 2M−1B = BRO(m , M )// M-bits BRO operationif B < L// only if B is smaller than L,   π (i) = B// B is used as the result of BRO interleaving for i  i= i+1end ifend for
TABLE 1B =MBRO(m, 5)ij = π(i)00001161162828324(pruning)4434520420612512728(pruning)826291871810108101126(pruning)1269613221022141411141530(pruning)161121171713171891491925(pruning)20515521211621221317132329(pruning)24318325191919261120112727(pruning)28721729232223301523153131(pruning)
Table 1 represents the result of the read address for interleaving using 5-bit BRO operation and pruning when L is equal to 24 (L=24). In case of L=24, since L is 24<L<5, 5-bit BRO operation of M=5 is used, and if the result of 5-bit BRO operation is greater than or equal to 24, pruning is performed. In Table 1, interleaving can be performed in such a manner that bits are output in the order of index i.
If L number of result values among result values of BRO operation performed for 2M decimal numbers of 0˜2M−1 are used for interleaving, pruning should be performed for 2M−L number of BRO operation result values. Accordingly, the maximum number of times of pruning of M-bit BRO interleaving for 2M-1<L≦2M is 2M−1, and the number of times of pruning increases if M becomes greater. If the number of times of pruning increases, problems occur in that system performance is deteriorated and additional complexity is caused.